This video introduces us to the Greedy Algorithms and its various Applications.
Codes:
- Minimum Coins
This track of the course covers the topic "Greedy Algorithms".
In details, this track will cover:
Objective: The objective of this track is to familiarize learners with Greedy Algorithms.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video introduces us to the Greedy Algorithms and its various Applications.
Codes:
This video discusses the Activity Selection Problem.
This video talks about C++ Solution of Activity Selection Problem.
Codes:
This video talks about Java Solution of Activity Selection Problem.
Codes:
This video discusses the Fractional Knapsack Problem.
This video talks about C++ implementation of Fractional Knapsack problem.
Codes:
This video talks about Java implementation of the Greedy Algorithm for Fraction Knapsack problem
Codes:
This video discusses the working and the concept behind the famous Job Sequencing Problem
Given a list of elements with specific values and weights associated with them, the task is to fill a Knapsack of weight W using these elements such that the value of knapsack is maximum possible.
Note: You are allowed to take a fraction of an element also in order to maximize the value.

At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.
Example 1: Consider the following 3 activities sorted by
finish time.
start[] = {10, 12, 20};
finish[] = {20, 25, 30};
A person can perform at most two activities. The
maximum set of activities that can be executed
is {0, 2} [ These are indexes in start[] and
finish[] ]
Example 2: Consider the following 6 activities
sorted by finish time.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The
maximum set of activities that can be executed
is {0, 1, 3, 4} [ These are indexes in start[] and
finish[] ]
Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30
Output: Following is maximum profit sequence of jobs
c, a
Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Output: Following is maximum profit sequence of jobs
c, a, e
1) Sort all jobs in decreasing order of profit.
2) Initialize the result sequence as the first job in sorted jobs.
3) Do following for remaining n-1 jobs
.......a) If the current job can fit in the current result sequence
without missing the deadline, add the current job to the result.
Else ignore the current job.
Following is maximum profit sequence of job : c a e
Asked In: Facebook Morgan Stanley
Asked In: Amazon Flipkart MakeMyTrip Microsoft
Asked In: Microsoft
Asked In: Microsoft
A | P, Q, R, S, T, U |
B | P, Q, R, U, S, T |
C | P, Q, R, U, T, S |
D | P, Q, T, R, U, S |